Consider the perceptron, then the GD update becomes

wt+1=wt−η∇wL|wt=wt+η1n∑i∈{misclassified}yixiw^{t+1} = w^t - \eta \nabla_w L \mid_{w^t} = w^t + \eta \frac{1}{n} \sum_{i \in \{\text{misclassified}\}} y_i x_i

and SGD update is based on a single misclassified data point,

wt+1=wt+yixiw^{t+1} = w^t + y_i x_i

The SGD update gives rise to an online perceptron algorithm:

  • intialize w0w^0 (at random, close to 00)
  • while not converged (no update (practically, within tolerance bound) is made to ww during one epoch or maximum iterations reached) do
    • pick up i∈{1,2,...,n}i \in \{1,2,...,n\} at random
    • if (yixiTwt≤0)(y_i x_i^T w^t \leq 0)

References

  1. Anna Choromanska. ECE-GY 7143 course slides, lecture 2.